//
// Created by madison on 2022/7/23.
//

#include <vector>

using namespace std;

/**
 * Definition for a binary tree node.
 **/
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:

    // 方法一：中序遍历，总是选择中间位置左边的数字作为根节点
    TreeNode *sortedArrayToBST(vector<int> &nums) {
        helper(nums, 0, nums.size() - 1);
    }

    TreeNode *helper(vector<int> &nums, int left, int right) {
        if (left > right) {
            return nullptr;
        }
        // 总是选择中间位置左边的数字作为根节点
        int mid = (left + right) / 2;
        TreeNode *root = new TreeNode(nums[mid]);

        root->left = helper(nums, left, mid - 1);
        root->right = helper(nums, mid + 1, right);
        return root;
    }

    // 方法二：中序遍历，总是选择中间位置右边的数字作为根节点
    TreeNode *sortedArrayToBST1(vector<int> &nums) {
        helper1(nums, 0, nums.size() - 1);
    }

    TreeNode *helper1(vector<int> &nums, int left, int right) {
        if (left > right) {
            return nullptr;
        }
        // 总是选择中间位置右边的数字作为根节点
        int mid = (left + right + 1) / 2;
        TreeNode *root = new TreeNode(nums[mid]);

        root->left = helper(nums, left, mid - 1);
        root->right = helper(nums, mid + 1, right);
        return root;
    }

    // 方法三：中序遍历，选择任意一个中间位置数字作为根节点
    TreeNode *sortedArrayToBST2(vector<int> &nums) {
        helper2(nums, 0, nums.size() - 1);
    }

    TreeNode *helper2(vector<int> &nums, int left, int right) {
        if (left > right) {
            return nullptr;
        }

        // 选择任意一个中间位置数字作为根节点
        int mid = (left + right + rand() % 2) / 2;
        TreeNode *root = new TreeNode(nums[mid]);

        root->left = helper(nums, left, mid - 1);
        root->right = helper(nums, mid + 1, right);
        return root;
    }
};

int main() {
    Solution solution;

    vector<int> nums = {-10, -3, 0, 5, 9};
    TreeNode *root = solution.sortedArrayToBST(nums);

    return 0;
}